package com.wlient.basic.LRU;

import lombok.NoArgsConstructor;
import org.omg.CORBA.NO_IMPLEMENT;
import org.springframework.util.StringUtils;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * @author: 史炜立
 * @description: least recent use 最近最少使用
 * @date: 2022/3/8 14:47
 */
public class LRUCache {

    class Node {
        Long key;
        String val;
        Node prev;
        Node next;
    }

    //模拟缓存容量
    private int capacity;

    //保存链表的头节点和尾节点
    private Node first;

    private Node last;

    //从key到node映射的map
    private Map<Long, Node> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>(capacity);
    }

    public String get(Long key) {
        Node node = map.get(key);
        if (node == null) {
            return null;
        }
        moveToHead(node);
        return node.val;

    }

    public void put(Long key, String val) {
        Node node = map.get(key);

        if (node == null){
            node = new Node();
            node.val = val;
            node.key = key;

            if(map.size() == capacity) {
                removeLast();
            }

            addToHead(node);

            map.put(key,node);


        }else {
            moveToHead(node);
            node.val = val;
        }

    }

    private void moveToHead(Node node) {
        if (node == first) {
            return;
        } else if (node == last) {
            last.prev.next = null;
            last = last.prev;
        } else {
            //如果是中间节点，中间节点的前节点的后指针  指向 中间节点的后节点
            //中间节点的后节点的前指针 指向 中间节点的前节点
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        //把该节点作为头结点
        node.prev = first.prev;// 写成node.prev = null;更好理解
        node.next = first;
        first.prev = node;
        first = node;
    }

    private void addToHead(Node node) {
        if (map.isEmpty()) {
            first = node;
            last = node;
        } else {
            //把新节点作为头结点
            node.next = first;
            first.prev = node;
            first = node;
        }
    }

    private void removeLast() {
        map.remove(last.key);
        Node prevNode = last.prev;
        //修改last所指的位置
        if (prevNode != null) {
            prevNode.next = null;
            last = prevNode;
        }
    }
    @Override
    public String toString() {
        return map.keySet().toString();
    }
    public static void main(String[] args) {
        LRUCache cache = new LRUCache(3);
        cache.put(1L,"A");
        cache.put(2L,"B");
        cache.put(3L,"C");
        System.out.println(cache);
        cache.get(1L);
        cache.get(8L);
        cache.put(9L,"M");
        cache.get(9L);
        System.out.println(cache);
    }
}
